A k-dissimilarity D on a finite set X, |X| >= k, is a map from the set ofsize k subsets of X to the real numbers. Such maps naturally arise fromedge-weighted trees T with leaf-set X: Given a subset Y of X of size k, D(Y) isdefined to be the total length of the smallest subtree of T with leaf-set Y .In case k = 2, it is well-known that 2-dissimilarities arising in this way canbe characterized by the so-called "4-point condition". However, in case k > 2Pachter and Speyer recently posed the following question: Given an arbitraryk-dissimilarity, how do we test whether this map comes from a tree? In thispaper, we provide an answer to this question, showing that for k >= 3 ak-dissimilarity on a set X arises from a tree if and only if its restriction toevery 2k-element subset of X arises from some tree, and that 2k is the leastpossible subset size to ensure that this is the case. As a corollary, we showthat there exists a polynomial-time algorithm to determine when ak-dissimilarity arises from a tree. We also give a 6-point condition fordetermining when a 3-dissimilarity arises from a tree, that is similar to theaforementioned 4-point condition.
展开▼
